package T213;

public class Main {
}

class Solution {
    public int rob(int[] nums) {
        if(nums.length==1) {
            return nums[0];
        }
        int n = nums.length;
        return Math.max(f1(nums, 2, n-2)+nums[0], f1(nums, 1, n-1));
    }
    private int f1(int[] nums, int l, int r) {
        if(l>r) {
            return 0;
        }
        if(l==r) {
            return nums[l];
        }
        if(l+1==r) {
            return Math.max(nums[l], nums[r]);
        }
        int prepre = nums[l];
        int pre = Math.max(nums[l+1], nums[l]);
        for(int i = l+2; i <= r; i++ ) {
            int cur = Math.max(pre, Math.max(nums[i]+prepre, nums[i]));
            prepre = pre;
            pre = cur;
        }
        return pre;
    }
}
